#include<iostream> 
using namespace std;

void Shell(int a[],int b,int t){//数据，增量，数据个数 
	int tem;
	 for(int i=b;i<t;i++){
	 	if(a[i]<a[i-b]){
	 		tem=a[i];
	 		int j=i-b;
	 		while(a[j]>tem&&j>=0){
	 			a[j+b]=a[j];
	 			j-=b;
			 }
			 a[j+b]=tem;
		 }
	 }
}

void Shellsort(int a[],int b[],int t){
	for(int i=10;i>=0;i--){
		Shell(a,b[i],t);
	}
	
}


int Qsort(int a[],int low,int high){
	int tem=a[low];
	while(low<high){
		while(a[high]>=tem&& high>low) high--;
		a[low]=a[high];
		while(a[low]<=tem && high>low) low++;
		a[high]=a[low];
	}
	a[low]=tem;
	return low;
}
void Quicksort(int a[],int low,int high) {
	if(low<high){
		int mid=Qsort(a,low,high);
		Quicksort(a,low,mid-1);
		Quicksort(a,mid+1,high);
	}
	
}

void Heapadjust(int a[],int min,int max){//范围 
	int root=min;
	int id=min;
	int tem=a[min];
	for(int i=min*2;i<=max;i*=2){
		if(i<max && a[i]<a[i+1]) i++;
		if(tem>=a[i]) break;
		a[i/2]=a[i];
		id=i;
	}
	a[id]=tem;
}
void Heapsort(int a[],int t){//a[o]不存储数据 ,大顶堆 
	for(int i=t/2;i>=1;i--)
		Heapadjust(a,i,t);
	int last=t;//最后一个的下标 
	while(last>=1){
		cout<<a[1]<<endl;
		int tem=a[last];
		a[last]=a[1];
		a[1]=tem;
		last--;
		Heapadjust(a,1,last);
	}
}


void Output(int a[],int t){
	cout<<"排序后为：";
	for(int i=0;i<t;i++){
		cout<<a[i]<<"\t";
	}
}

int main()
{
	int a[10000]; 
	int t;// 
	int b[15]={1,3,5,7,11,13,19,23,29};
	
	cout<<"希尔排序，请输入数据个数n，和n个数据\n";
	cin>>t;
	for(int i=0;i<t;i++){
		cin>>a[i];
	} 
	Shellsort(a,b,t);
	Output(a,t);
	
	cout<<"\n快速排序，请输入数据个数n，和n个数据\n"; 
	cin>>t;
	for(int i=0;i<t;i++){
		cin>>a[i];
	}
	Quicksort(a,0,t-1); 
	Output(a,t);
	
	cout<<"\n堆排序，请输入数据个数n，和n个数据\n"; 
	cin>>t;
	for(int i=1;i<=t;i++){
		cin>>a[i];
	}
	Heapsort(a,t);
	
	return 0;
}
